package com.fun.arithmetic;

import java.util.Arrays;

/**
 * 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
 *
 * 换句话说，s1 的排列之一是 s2 的 子串 。
 *
 * 有个前提，都是小写字母
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/permutation-in-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class StringContains {
    public static void main(String[] args) {
        String s1="ab";
        String s2= "ikmnb";
        System.out.println(checkInclusion(s1,s2));
    }

    /**
     * 例如：s1 = "ab"，s2="ikbacc"
     * 基本思路：滑动窗口法
     * 创建两个数组，代表s1在26个字母中的位置，s2在26个字母中的位置，然后比较数组是否相等
     * 在S2中滑动进行比较
     */
    public static boolean checkInclusion(String s1,String s2){
        int[] array1=new int[26];
        int[] array2=new int[26];
        int len1 = s1.length();
        int len2 = s2.length();

        //初始化，并开始比较第一段
        for (int i = 0; i < len1; i++) {
            ++array1[s1.charAt(i)-'a'];
            ++array2[s2.charAt(i)-'a'];
        }
        if(Arrays.equals(array1,array2)){
            return true;
        }

        for (int i=len1;i<len2;i++){
            ++array2[s2.charAt(i)-'a'];
            --array2[s2.charAt(i-len1)-'a'];
            if(Arrays.equals(array1,array2)){
                return true;
            }
        }
        return false;
    }
}
